package ACwing.P4Math.FastPower;

import java.io.*;

/**
 * @Date : 2023-03-22
 * @Description:AcWing 875. 快速幂
 * 时间复杂度a^k   从o(k)到 o(logk)
 * a^(2^0)*a^(2^1)……a^(2^log2k)  共logk
 * ak=a^^(2^i)*a^(2^j)……
 *      =a^(2^i+2^j+……）
 *      比如(k)2=(11010)
 *      k=2^5+2^4+2^1
 *
 *
 *
 */
public class FastPow {
    static int n;
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
         n = Integer.parseInt(br.readLine());
        long a,b,p;
        while (n--!=0){
            String[] strings = br.readLine().split("\\s+");
            a = Long.parseLong(strings[0]);
            b = Long.parseLong(strings[1]);
            p = Long.parseLong(strings[2]);
           bw.write(String.valueOf(qmi(a,b,p)));
           bw.newLine();
        }
        bw.flush();

    }

    //返回a^b%p的结果
    static long  qmi(long a,long b,long p){
        long res=1;
        while(b!=0){  //求b的二进制表示
            if((b&1)==1) res=res*a%p;
            b>>=1;//删掉末尾
            a=a*a%p;
        }
        return res;
    }
}
